Puu (andmestruktuur)

See artikkel ootab keeletoimetamist. (Veebruar 2019) Kui oskad, siis palun aita artiklit keeleliselt parandada. (Kuidas ja millal see märkus eemaldada?)

Puu on infotehnoloogias hierarhiline andmestruktuur, kus andmed on paigutatud puukujuliselt.

Puu koosneb tippudest (nodes) ja kaartest (edges), mis ühendavad tippe (viited). Tipud, mis on ühendatud kaarega üleval asuva tipu külge on lapsed (childs) ja üleval asuv tipp on sel juhul vanem (parent). Kõige ülemine tipp on juur (root). Tippu, millel ei ole lapsi, nimetatakse leheks (leaf). Liikudes tipust vanemasse, sealt vanemasse jne jõuame juurde. Esivanemad on kõik tipud, mis jäävad tipu ja vaadeldava juures vahepeale.

Puu kõrgus (tree height) on pikim tee lehest juureni. Järjestatud puu korral on defineeritud juur ja otse juurega ühendatud tipud on esimese taseme tipud (first level nodes, juure lapsed), esimese taseme tippudega otse ühendatud tipud on teise taseme tipud (esimese taseme tippude lapsed) jne ning laste järjekord vasakut paremale on oluline. Mets on vähemalt kahest puust koosnev puude kogum.^[1]